package org.springside.modules.utils;


public  class LCS {
	public int longestSubstr(String str_, String toCompare_) 
	{
	  if (str_.isEmpty() || toCompare_.isEmpty())
	    return 0;
	 
	  int[][] compareTable = new int[str_.length()][toCompare_.length()];
	  int maxLen = 0;
	 
	  for (int m = 0; m < str_.length(); m++) 
	  {
	    for (int n = 0; n < toCompare_.length(); n++) 
	    {
	      compareTable[m][n] = (str_.charAt(m) != toCompare_.charAt(n)) ? 0
	          : (((m == 0) || (n == 0)) ? 1
	              : compareTable[m - 1][n - 1] + 1);
	      maxLen = (compareTable[m][n] > maxLen) ? compareTable[m][n]
	          : maxLen;
	    }
	  }
	  return maxLen;
	}

}
